#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 6e6+3;
const LL MOD = 998244353;

LL ps[20], psc;
void Feijie(LL n) {
    LL len = sqrt(n);
    psc=0;
    for (LL i=2; i<=len; ++i) {
        if (n%i==0) {
            ps[psc++] = i;
            while (n%i==0) n /= i;
        }
    }
    if (n!=1) ps[psc++] = n;
}
LL FastPOW(LL a, LL k) {
    LL ret = 1;
    while (k) {
        if (k&1) {
            ret = (ret * a) % MOD;
        }
        k = (k>>1);
        a = (a*a) % MOD;
    }
    return ret;
}
LL solve(LL n, LL k) {
    Feijie(n);
    LL len = (1<<psc);
    LL ret = 0;
    for (LL i=0; i<len; ++i) {
        LL d = 1;
        LL cnt = 0;
        for (LL j=0; j<psc; ++j) {
            if (i&(1<<j)) {
                ++cnt;
                d *= ps[j];
            }
        }
        if (cnt&1) ret = (ret - FastPOW(n/d, k)) % MOD;
        else ret = (ret + FastPOW(n/d, k)) % MOD;
    }
    if (ret<0) ret+=MOD;
    return ret;
}


int main() {
    LL m, k;
    while (~scanf("%lld %lld", &m, &k)) {
        LL n;
        while (m--) {
            scanf("%lld", &n);
            if (n==0) {
                printf("0\n");
                continue;
            }
            printf("%lld\n", solve(n, k));
        }
    }
    return 0;
}
